package com.zhy.algorithm;


/**
 * @author 随缘而愈
 * @version 1.0
 * @description 狄克斯特拉算法
 * @date 2024/7/15 15:36
 */

public class DijkstraAlgorithm {
    public static void main(String[] args) {
        int graph[][] = new int[][] {
                {0, 4, 0, 0, 0, 0, 0, 8, 0},
                {4, 0, 8, 0, 0, 0, 0, 11, 0},
                {0, 8, 0, 7, 0, 4, 0, 0, 2},
                {0, 0, 7, 0, 9, 14, 0, 0, 0},
                {0, 0, 0, 9, 0, 10, 0, 0, 0},
                {0, 0, 4, 14, 10, 0, 2, 0, 0},
                {0, 0, 0, 0, 0, 2, 0, 1, 6},
                {8, 11, 0, 0, 0, 0, 1, 0, 7},
                {0, 0, 2, 0, 0, 0, 6, 7, 0}
        };
        int startVertex = 0;
        dijkstra(graph, startVertex);
    }

    public static void dijkstra(int[][] graph, int startVertex) {
        int n = graph.length;
        int[] distance = new int[n];
        boolean[] visited = new boolean[n];

        // 初始化距离数组
        for (int i = 0; i < n; i++) {
            distance[i] = graph[startVertex][i];
        }

        // 标记起始顶点为已访问
        visited[startVertex] = true;

        for (int i = 0; i < n - 1; i++) {
            // 找到未被访问过的顶点中距离起始顶点最近的顶点
            int minDistance = Integer.MAX_VALUE;
            int nearestVertex = -1;
            for (int j = 0; j < n; j++) {
                if (!visited[j] && distance[j] < minDistance) {
                    minDistance = distance[j];
                    nearestVertex = j;
                }
            }

            // 将找到的顶点标记为已访问
            visited[nearestVertex] = true;

            // 更新距离数组
            for (int j = 0; j < n; j++) {
                if (!visited[j]) {
                    int newDistance = distance[nearestVertex] + graph[nearestVertex][j];
                    if (newDistance < distance[j]) {
                        distance[j] = newDistance;
                    }
                }
            }
        }

        // 输出结果
        for (int i = 0; i < n; i++) {
            System.out.println("从顶点" + startVertex + "到顶点" + i + "的最短距离为：" + distance[i]);
        }
    }
}